using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0632. 最小区间")]
    public class No0632_SmallestRange : AbsBaseTestItem
    {
        /*
        你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
        我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

        示例 1:
        输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
        输出: [20,24]
        解释:
        列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
        列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
        列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

        注意:
            给定的列表可能包含重复元素，所以在这里升序表示 >= 。
            1 <= k <= 3500
            -105 <= 元素的值 <= 105
        */

        public override void OnTest()
        {
            Assert.TestExe(SmallestRange,
                new List<IList<int>>() {
                    new List<int>() {4,10,15,24,26},
                    new List<int>() {0,9,12,20},
                    new List<int>() {5,18,22,30},
                },
                new int[] { 20, 24 });
        }

        public int[] SmallestRange(IList<IList<int>> nums)
        {
            int size = nums.Count;
            Dictionary<int, IList<int>> indices = new Dictionary<int, IList<int>>();
            int xMin = int.MaxValue, xMax = int.MinValue;
            for (int i = 0; i < size; i++)
            {
                foreach (int x in nums[i])
                {
                    IList<int> list = indices.GetValueOrDefault(x) ?? new List<int>();
                    list.Add(i);
                    indices[x] = list;
                    xMin = Math.Min(xMin, x);
                    xMax = Math.Max(xMax, x);
                }
            }

            int[] freq = new int[size];
            int inside = 0;
            int left = xMin, right = xMin - 1;
            int bestLeft = xMin, bestRight = xMax;

            while (right < xMax)
            {
                right++;
                if (indices.ContainsKey(right))
                {
                    foreach (int x in indices[right])
                    {
                        freq[x]++;
                        if (freq[x] == 1)
                        {
                            inside++;
                        }
                    }
                    while (inside == size)
                    {
                        if (right - left < bestRight - bestLeft)
                        {
                            bestLeft = left;
                            bestRight = right;
                        }
                        if (indices.ContainsKey(left))
                        {
                            foreach (int x in indices[left])
                            {
                                freq[x]--;
                                if (freq[x] == 0)
                                {
                                    inside--;
                                }
                            }
                        }
                        left++;
                    }
                }
            }
            return new int[] { bestLeft, bestRight };
        }
    }
}
